package exam.microsoft.first.task3;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: 18362
 * @Create: 2022-08-19 18:57:18 星期五
 */
class Solution {
    private List<Integer>[] graph;
    private int res;
    public int solution(int[] A, int[] B) {
        buildGraph(A, B);
        dfs(0, new boolean[A.length+1]);
        return res;
    }

    private void buildGraph(int[] A, int[] B) {
        int n = A.length + 1;
        graph = new List[n];
        for (int i=0; i<graph.length; ++i)
            graph[i] = new ArrayList<>();
        for (int i = 0; i<A.length; ++i) {
            graph[A[i]].add(B[i]);
            graph[B[i]].add(A[i]);
        }
    }

    private int dfs(int cur, boolean[] isv) {
        isv[cur] = true;
        int w = 0;
        for (int i=0; i<graph[cur].size(); ++i) {
            int v = graph[cur].get(i);
            if (!isv[v]) {
                int p = dfs(v, isv);
                res += ((p - 1) / 5 + 1);
                w += p;
            }
        }
        return w+1;
    }
}
